package main.Q801_900;

import java.util.ArrayList;
import java.util.List;

public class Q831_840 {
    public static void main(String[] args) {
        System.out.println("Question831：");
        System.out.println("Question832：翻转图像");
        System.out.println("Question833：");
        System.out.println("Question834：");
        System.out.println("Question835：");
        System.out.println("Question836：");
        System.out.println("Question837：");
        System.out.println("Question838：");
        System.out.println("Question839：相似字符串组");
        System.out.println("Question840：");
    }
}

class Question832{
    public int[][] flipAndInvertImage(int[][] image) {
        int n = image.length;
        for (int i = 0; i < n; i++) {
            int left = 0, right = n - 1;
            while (left < right) {
                if (image[i][left] == image[i][right]) {
                    image[i][left] ^= 1;
                    image[i][right] ^= 1;
                }
                left++;
                right--;
            }
            if (left == right) {
                image[i][left] ^= 1;
            }
        }
        return image;
    }
}

class Question839{
    int[] parents;
    public boolean process(char[] str1,char[] str2){//判断相似
        List<Integer> list=new ArrayList<>();
        for (int i=0;i< str2.length;i++){
            if (str1[i]!=str2[i]) {
                list.add(i);
            }
        }
        if (list.size()==0) return true;
        if (list.size()==2&&str1[list.get(0)]==str2[list.get(1)]&&str1[list.get(1)]==str2[list.get(0)]) return true;
        return false;
    }

    public int find(int i){
        while (parents[i]!=i){
            i=parents[i];
        }
        return i;
    }

    public void  union(int i,int j){
        parents[find(i)]=find(j);
    }

    public int numSimilarGroups(String[] strs) {
        char[][] words=new char[strs.length][];
        parents=new int[strs.length];
        int brunch= words.length;
        for (int i=0;i< words.length;i++) parents[i]=i;
        for (int i=0;i< strs.length;i++){
            words[i]=strs[i].toCharArray();
        }
        for (int i=0;i< words.length;i++){
            for (int j=i+1;j< words.length;j++){
                if (process(words[i],words[j])&&find(i)!=find(j)){//相似且为合并
                    union(i,j);
                    brunch--;
                }
            }
        }
        return brunch;
    }
}